package io.github.hadyang.leetcode.random;

import com.sun.javafx.font.coretext.CTFactory;
import org.junit.Test;

import java.util.HashSet;
import java.util.Set;

/**
 * 给定一个长度为 n 的整数数组，你的任务是判断在最多改变 1 个元素的情况下，该数组能否变成一个非递减数列。
 *
 * <p>我们是这样定义一个非递减数列的： 对于数组中所有的 i (1 <= i < n)，满足 array[i] <= array[i + 1]。
 *
 * <p>示例 1:
 *
 * <p>输入: [4,2,3] 输出: True 解释: 你可以通过把第一个4变成1来使得它成为一个非递减数列。 示例 2:
 *
 * <p>输入: [4,2,1] 输出: False 解释: 你不能在只改变一个元素的情况下将其变为非递减数列。 说明:  n 的范围为 [1, 10,000]。
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/non-decreasing-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Q665 {

  public boolean checkPossibility(int[] nums) {
    if (nums.length <= 2) return true;

    int s2 = -1; // 第二个非递减序列的下标
    for (int i = 1; i < nums.length; i++) {
      if (nums[i - 1] > nums[i]) {

        // 出现第三个非递减序列 -> 数组不可能替换为非递减
        if (s2 != -1) {
          return false;
        }

        s2 = i;
      }
    }

    // s2 不存在 -> 数组非递减
    if (s2 == -1) {
      return true;
    }

    // 第一个非递减序列结束的下表
    int e1 = s2 - 1;

    // 第一个非递减序列只有一个，或者 e1 左右为非递减
    if (e1 - 1 < 0 || nums[e1 - 1] <= nums[e1 + 1]) {
      return true;
    }

    // 第二个非递减序列只有一个，或者 s2 左右为非递减
    if (s2 + 1 == nums.length || nums[s2 - 1] <= nums[s2 + 1]) {
      return true;
    }

    return false;
  }

  @Test
  public void test() {
    System.out.println(checkPossibility(new int[] {4, 2, 3})); // true
    System.out.println(checkPossibility(new int[] {4, 2, 1})); // false
    System.out.println(checkPossibility(new int[] {3, 4, 2, 3})); // false
    System.out.println(checkPossibility(new int[] {-1, 4, 2, 3})); // true
    System.out.println(checkPossibility(new int[] {2, 3, 3, 2, 4})); // true
  }
}
